package other;

import java.util.Queue;

public class repeatedSubstringPattern_459 {

    //假设字符串s是由s1+s2+ s3组成的，s+s后，str就变成了s1+s2+ s3 + s1+s2+ s3
    // 去掉首尾，破环了首尾的s1和s3，变成了s4+s2+ s3 +s1+ s2 +s5,此时str中间就是s2+ s3 +s1+ s2
    // 如果s是循环字串，也就是s1=s2=s3,所以str中间的s2+ s3 +s1 或者s3 +s1+ s2 就和原字符串相等。
    public boolean repeatedSubstringPattern(String s) {
        char[] arr = new char[2 * s.length() - 2];
        int index = 0;
        for (int i = 1; i < s.length(); i++)
            arr[index++] = s.charAt(i);
        for (int i = 0; i < s.length() - 1; i++)
            arr[index++] = s.charAt(i);
        int[] next = new int[s.length()];
        getNext(next, s);
        int j = 0;
        for (int i = 0; i <arr.length; i++) {
            while (j > 0 && arr[i] != s.charAt(j))
                j = next[j - 1];
            if (arr[i] == s.charAt(j))
                j++;
            if (j == s.length())  //说明找到了s
                return true;
        }
        return false;
    }

    public void getNext(int[] next, String s) {
        int pre = 0, i = 1;
        while (i < s.length()) {
            if (s.charAt(i) == s.charAt(pre)) {
                pre++;
                next[i] = pre;
                i++;
            } else {
                if (pre == 0) {
                    next[i] = 0;
                    i++;
                } else
                    pre = next[pre - 1];
            }

        }
    }
}
